package quickSort;

import java.util.Stack;

/**
 *
 *  快排： 以下是几种快排的方法 优先用挖坑法
 *  时间复杂度: 理想情况：O(N * log n)
 *            最慢：O(N^2),有序或者逆序时，其次如果数据过多，因为是递归，可能出现栈溢出的错误
 *            如何优化呢？？？
 *  空间复杂度: O(log n)
 *  稳定性: 不稳定的排序
 *  场景：排序无序的数据
 *
 */


public class MyQuickSort {
    /**
     *  优化的快速排序：优化可能出现栈溢出的错误 <排序3 00：21：00> 讲解
     *  解决方案1：随机选取基准法
     *  解决方案2：三数取中法 --> 使时间复杂度趋于N * log n
     */
    //三数取中法：以挖坑法来优化
    private static int midValueIndex(int[] array,int left,int right) {
        //求三个数中的中位数的下标
        int mid = (left + right) >>> 1;
        if(array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            }else if (array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if (array[mid] < array[right]) {
                return right;
            }else if (array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }

    /**
     *  快排的二次优化：为了减少递归次数，当数据较少时，可使用直接插入排序
     *              主要优化了递归的深度
     */
    private static void quickInsertSort(int[] array,int start,int end) {
        //快排专用插入排序：需要指定区间
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start; j--) {
                //加上等号就变成不稳定，但算法本身还是有序的
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     *  2.挖坑法
     */
    private static int partitionHole(int[] array,int start,int end) {
        int key = array[start]; //"坑"的值
        while(start < end) {
            //array[end] >= key 为什么取等号 ？ -->不取等号会死循环！下同。
            while(start < end && array[end] >= key) {
                end--;
            }
            array[start] = array[end]; //填坑
            while(start < end && array[start] <= key) {
                start++;
            }
            array[end] = array[start]; //填坑
        }
        array[start] = key;
        return start;
    }


    /**
     *  1.Hoare法 --> 找基准  课程排序2 中的 02：20：00左右讲解
     */
   //找基准的函数 : Hoare法 -》找基准
   // 左边做key,先走左边，那么start与end相遇的那个数据比基准大，因此要先走右边（此处是升序）
    private static int partitionHoare(int[] array,int start,int end) {
        int index = start; //基准的下标
        int key = array[start]; //基准值
        while(start < end) {
            //array[end] >= key 为什么取等号 ？ -->不取等号会死循环！下同。
            while(start < end && array[end] >= key) {
                //如果 基准 右边的值都不比 基准小，那么end 会一直减，会出现数组越界
                //所以判断条件不能只是array[end] >= key，应该是 start < end && array[end] >= key
                end--;
            }
            //左边做key，先走右边(end),再走左边(start)
            while(start < end && array[start] <= key) {
                start++;
            }
            //交换
            swap(array,start,end);
        }
        swap(array,start,index);
        return end;
    }

    /**
     *  前后指针法：
     */
    private static int partitionPoint(int[] array,int start,int end) {
         int prev = start;
         int cur = start + 1;
         while(cur <= end) {
             if(array[cur] < array[start] && array[++prev] != array[cur]) {
                 swap(array,cur,prev);
             }
             cur++;
         }
        swap(array,prev,start);
        return prev;
    }



    public static void quickSort(int[] array) {
        //quickSortChild(array,0,array.length-1); //递归实现
        quickSortStack(array); //非递归（栈）实现
    }

    //快排的主要代码实现:利用递归
    private static void quickSortChild(int[] array,int left,int right) {
        if(left >= right) { return; }

        //主要优化了递归的深度
       if(right - left + 1 <= 7) {
            //快排的二次优化 : 使用直接插入排序
           quickInsertSort(array,left,right);
            return;
        }

        //
        //这里是三数取中法的优化 ：优化了递归的深度，并使时间复杂度趋于N * log n
        int index = midValueIndex(array,left,right);//中位数的下标
        swap(array,left,index);
        //

        int pivot = partitionHole(array,left,right); //pivot 是基准
        quickSortChild(array,left,pivot-1);
        quickSortChild(array,pivot+1,right);
    }
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    /**
     *  非递归实现 快排 ：利用栈 --> 挖坑法为例
     *  排序3-》01：13：00 左右讲解
     */
    public static void quickSortStack(int[] array) {

        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;

        //三数取中优化
        int index = midValueIndex(array,left,right);//中位数的下标
        swap(array,left,index);

        int pivot = partitionHoare(array,left,right);

        //基准左边 入栈
        if(pivot > left + 1) {
            //基准左边至少有两个元素才入栈
            stack.push(left);
            stack.push(pivot - 1);
        }
        //基准右边 入栈
        if(pivot < right - 1) {
            //基准右边 至少有两个元素才入栈
            stack.push(pivot + 1);
            stack.push(right);
        }

        while(!stack.empty()) {
            right = stack.pop();
            left = stack.pop();

            //三数取中优化
            index = midValueIndex(array,left,right);//中位数的下标
            swap(array,left,index);

            pivot = partitionHoare(array,left,right);

            //基准左边 入栈
            if(pivot > left + 1) {
                //基准左边至少有两个元素才入栈
                stack.push(left);
                stack.push(pivot - 1);
            }
            //基准右边 入栈
            if(pivot < right - 1) {
                //基准右边 至少有两个元素才入栈
                stack.push(pivot + 1);
                stack.push(right);
            }
        }

    }
}
